#include <iostream>
#include <vector>
#include <Vector.hpp>
using namespace std;

class Solution
{
public:
    vector<int> longestObstacleCourseAtEachPosition(vector<int> &obstacles)
    {
        vector<int> res;
        vector<int> end;
        for (int i = 0; i < obstacles.size(); i++)
        {
            int maxlen = 0;
            if (end.empty())
            {
                end.push_back(obstacles[i]);
                maxlen = 1;
            }
            else
            {
                int left = 0, right = end.size() - 1;
                if (obstacles[i] >= end.back())
                {
                    end.push_back(obstacles[i]);
                    left = end.size() - 1;
                }
                else
                {
                    do
                    {
                        int mid = (left + right) / 2;
                        if (end[mid] <= obstacles[i])
                            left = mid + 1;
                        else
                            right = mid;
                    } while (left < right);
                    end[left] = obstacles[i];
                }
                maxlen = left + 1;
            }
            res.push_back(maxlen);
        }
        return res;
    }
};

int main()
{
    cout << "Code1964" << endl;
    Solution s;
    // vector<int> obs = {3, 1, 5, 6, 4, 2};
    vector<int> obs = {2, 2, 1};
    auto res = s.longestObstacleCourseAtEachPosition(obs);
    PrintVector(res);
    return 0;
}